/*
 * @lc app=leetcode.cn id=187 lang=java
 *
 * [187] 重复的DNA序列
 */

// @lc code=start

import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        // 使用HashSet存储所有长度为10的子串，如果已经存在则加入到结果集中
        // 用滑动窗口来实现

        List<String> res = new ArrayList<>();

        int n = s.length();
        Map<String, Integer> map = new HashMap<>();

        for(int i = 0; i+10 <= n; i++) {
            String sub = s.substring(i, i+10);
            int count = map.getOrDefault(sub, 0);

            if(count == 1) {
                res.add(sub);
            }
            map.put(sub, count + 1);
        }
        return res;
    }
}
// @lc code=end

